Combinatorial optimisation problems arise when allocating resources to tasks so as to maximise the benefits. Typical examples of combinatorial optimisation problems are: scheduling to meet the most possible due dates; rostering to meet personnel constraints and avoid unnecessary overtime; allocation of vehicles or machines to journeys or jobs so as to minimise cost; routing, cutting, packing and scheduling problems; many bioinformatics problems, and any combination of the above.
Dynamic programming is a powerful technique for solving optimization problems efficiently. Dynamic programming is a widely-used operational algorithm for solving classes of optimisation problems that can be divided into stages or sub-problems. This form of algorithm finds all “good” solutions to each stage, and builds on solutions of the previous stage when solving the next stage. Dynamic programming requires that the problem has the optimal substructure property, that is, one can create an optimal solution to a problem using only the optimal solutions of its sub-problems. FIG. 1 illustrates usual compilation and execution of a dynamic program. One reason that dynamic programming is popular is that dynamic programming solutions are typically easier to implement than other optimization approaches, since it simply requires functions and memoing. A dynamic program is considered herein as simply being a recursive program that is evaluated with memoization and lookup of answers. A classic example of a dynamic program is 0-1 knapsack.
A machine-readable medium includes any mechanism that provides (i.e. stores and/or transmits) information in a form readable by a machine (e.g. a computer). For example a machine-readable medium includes read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; electrical, optical, acoustical or other form of prompted signals (e.g. carrier waves, infrared signals, digital signals, etc.).